In many conventional memory systems, such as random access memory, binary digits (bits) are stored in memory cells, and are accessed by a processor that specifies a linear address that is associated with the given cell. This system provides rapid access to any portion of the memory system within certain limitations. To facilitate processor control, each operation that accesses memory must declare, as a part of the instruction, the address of the memory cell/cells required. Standard memory systems are not well designed for a content based search. Content based searches in standard memory require software based algorithmic search under the control of the microprocessor. Many memory operations are required to perform a search. These searches are neither quick nor efficient in using processor resources.
To overcome these inadequacies an associative memory system called Content Addressable Memory (CAM) has been developed. CAM allows cells to be referenced by their contents, so it has first found use in lookup table implementations such as cache memory subsystems and is now rapidly finding use in networking systems. CAM's most valuable feature is its ability to perform a search and compare of multiple locations as a single operation, in which search data is compared with data stored within the CAM. Typically search data is loaded onto search lines and compared with stored words in the CAM. During a search-and-compare operation, a match or mismatch signal associated with each stored word is generated on a matchline, indicating whether the search word matches a stored word or not.
A CAM stores data in a matrix of cells, which are typically SRAM based cells or DRAM based cells. Until recently, SRAM based CAM cells have been most common because of their simple implementation. However, to provide ternary state CAMs, i.e. where each CAM cell can store one of three values: a logic “0”, “1” or “don't care” result, ternary SRAM based cells typically require many more transistors than ternary DRAM based cells. As a result, ternary SRAM based CAMs have a much lower packing density than ternary DRAM based cells.
A typical CAM block diagram is shown in FIG. 1. The CAM 10 includes a matrix, or array 25, of DRAM based CAM cells (not shown) arranged in rows and columns. An array of DRAM based ternary CAM cells have the advantage of occupying significantly less silicon area than their SRAM based counterparts. A predetermined number of CAM cells in a row store a word of data. An address decoder 17 is used to select any row within the CAM array 25 to allow data to be written into or read out of the selected row. Data access circuitry such as bitlines and column selection devices, are located within the array 25 to transfer data into and out of the array 25. Located within CAM array 25 for each row of CAM cells are matchline sense circuits, which are not shown, and are used during search-and-compare operations for outputting a result indicating a successful or unsuccessful match of a search word against the stored word in the row. The results for all rows are processed by the priority encoder 22 to output the address (Match Address) corresponding to the location of a matched word. The match address is stored in match address registers 18 before being output by the match address output block 19. Data is written into array 25 through the data I/O block 11 and the various data registers 15. Data is read out from the array 25 through the data output register 23 and the data I/O block 11. Other components of the CAM include the control circuit block 12, the flag logic block 13, the voltage supply generation block 14, various control and address registers 16, refresh counter 20 and JTAG block 21.
FIG. 2 shows a typical ternary DRAM type CAM cell 30 as described in issued U.S. Pat. No. 6,320,777 B1. DRAM CAM Cell 30 has a comparison circuit which includes an n-channel search transistor 32 connected in series with an n-channel compare transistor 34 between a matchline ML and a tail line TL. A search line SL* is connected to the gate of search transistor 32. The storage circuit includes an n-channel access transistor 36 having a gate connected to a wordline WL and connected in series with storage capacitor 38 between bitline BL and a cell plate voltage potential VCP. Charge storage node CELL1 is connected to the gate of compare transistor 34 to turn on transistor 34 if there is charge stored on capacitor 38 representative of a logic “1” state. The remaining transistors and capacitor mirror transistors 32, 34, and 36 and capacitor 38 for the other half of the ternary data bit, and are connected to corresponding lines SL and BL* and are provided to support ternary data storage. Together they can store a ternary value representing logic “1”, logic “0”, or “don't care”. Table 1 below shows the possible ternary states cell 30 can assume.
TABLE 1Ternary ValueCELL1CELL2001110“Don't Care”00
The tail line TL is typically connected to ground and all the transistors are n-channel transistors. The description of the operation of the ternary DRAM cell is detailed in the aforementioned issued U.S. Pat. No. 6,320,777 B1.
Another commonly used type of memory cell is a binary cell as shown in FIG. 3. Binary CAM cell 40 is identical to ternary cell 30 of FIG. 2 except that a latching storage element is used instead of a pair of DRAM storage cells. While search transistor 42, compare transistor 44 and access transistor 46 correspond to transistors 32, 34 and 36 respectively, a first inverter 48 and a second inverter 50 are arranged in a cross-coupled configuration. The input of inverter 48 is connected to the gate of compare transistor 44 and a source/drain terminal of access transistor 46. The input of inverter 50 is thus connected to the same transistors of the duplicate half of cell 40. Binary cell 40 is well known in the art, and is essentially an SRAM cell with two pairs of search and compare transistors connected to the complementary terminals of the cross-coupled inverters.
CAMs are designed to allow very fast searching of large amounts of data, organized as words. Active CAMs in networking systems typically spend 90% of their time executing searches and 10% of the time executing table maintenance functions. Table maintenance includes writing new entries and deleting old entries from the memory array.
CAMs typically store data in 72 bit or 144 bit segments called words, where each word is stored on a single row of cells within the CAM array. However there is a developing need to store larger increments of data such as 288 bit and 432 bit words. Since it may not be practical to fabricate CAM memory arrays with 288 or 432 bit rows, these wide words are stored in multiple consecutive rows. For example, to store a 288 bit word in a CAM array with a row size of 72 bits would require four consecutive rows. Storing and searching wide words in multiple of rows can be done without significant overhead over searching normal sized words. However, deleting wide word entries can consume a large number of cycles.
Prior art CAMs disclosed in U.S. Pat. No. 6,246,601 (Pereira et al.) or U.S. patent application Ser. No. 09/997,296 (Gillingham) assigned to Mosaid Technologies Inc. can each store and search for wide words in an efficient manner. However deleting or purging those entries can not be performed in an efficient manner. In the Pereira et al. CAM system, the system controller first has to search for the location of the wide word entry. The system controller would have to wait for the search result before calculating the location of the first word. A delete command is then issued for that word and then all subsequent segments that make up the wide word. Because a CAM only provides the highest priority match address, copies of the deleted wide word can still reside in the CAM array. Therefore, the system controller would have to repeat the search to ensure that no other copies of the wide word have been stored. In a case where there are 100 wide words each consisting of 4 word segments to be deleted, at least 1200 cycles will be required to delete all 100 wide words. More specifically, four cycles are required to search for each wide word, four cycles each to delete the wide word and four more to search the CAM again to ensure all copies of that wide word were deleted.
Hence if table maintenance operations consume too many cycles of the CAM device, then its search performance is degraded as these cycles are not available for executing search operations. Therefore the overhead for deleting wide words stored in multiple segments is significant in prior art CAM devices. Therefore to increase overall CAM performance, the number of CAM cycles required for table maintenance operations should be minimized.
Therefore, there is a need for a CAM that can efficiently search and delete wide word entries.